// https://leetcode.cn/problems/game-of-life/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int dir[8][2] = {
            {0, 1}, {1, 1}, {1, 0}, {-1, 1},
            {-1, 0}, {-1, -1}, {0, -1}, {1, -1}
        };

        int m = board.size();
        int n = board[0].size();
        vector<vector<int>> tmp(m, vector<int>(n));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i][j] = board[i][j];
                
                if (board[i][j]) {
                    int count = 0;

                    for (int k = 0; k < 8; k++) {
                        int nextRow = i + dir[k][0];
                        int nextCol = j + dir[k][1];
                        
                        if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n) {
                            count += board[nextRow][nextCol];
                        }
                    }

                    if (count < 2 || count > 3) {
                        tmp[i][j] = 0;
                    }
                } else {
                    int count = 0;

                    for (int k = 0; k < 8; k++) {
                        int nextRow = i + dir[k][0];
                        int nextCol = j + dir[k][1];
                        
                        if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n) {
                            count += board[nextRow][nextCol];
                        }
                    }

                    if (count == 3) {
                        tmp[i][j] = 1;
                    }
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = tmp[i][j];
            }
        }
    }
};